package leetcode.editor.cn;

import leetcode.editor.cn.common.ListNode;

/**
 * @Author: Dempsey
 * @Data: 2021-03-15 18:24:52
 */

//给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 
//将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 
//
// 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 示例 1: 
//
// 给定链表 1->2->3->4, 重新排列为 1->4->2->3. 
//
// 示例 2: 
//
// 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. 
// Related Topics 链表 
// 👍 534 👎 0


public class P143 {
    public static void main(String[] args) {
        Solution solution = new P143().new Solution();
    }

//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public void reorderList(ListNode head) {
			// 第一，我要知道链表长度，我要移动的是后一半（可以用快慢指针找链表中点
            // 第二，我要后一半的逆序，用于插入

            if (head == null || head.next == null || head.next.next == null) return;

            // 1. 找中点，让slow指向中点，或左中点位置
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            // 2. 断开中点，反转后半部分
            ListNode head2 = null, next = slow.next;
            slow.next = null;
            slow = next;
            while (slow != null) {
                next = slow.next;
                slow.next = head2;
                head2 = slow;
                slow = next;
            }

            // 3. 合并链表head和head2
            ListNode curr = head;
            ListNode curr2 = head2;
            while (curr != null && curr2 != null) {
                next = curr.next;
                curr.next = curr2;
                curr2 = curr2.next;
                curr.next.next = next;
                curr = next;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}